#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <string>



using namespace std;

// Diccionario
char toChar[10] = {'0','1','2','3','4','5','6','7','8','9'};

// Estructura para el nodo.
struct nodoTrie{
    int id; // Nombre
    bool esHoja; // Para ver si el nodo es hoja del trie
    string bill; // El bill asociado a la clave
    int cantHijos;// Cantidad de hijos del Nodo
    struct nodoTrie *hijos[10]; // Los hijos    
};
typedef struct nodoTrie trie; // Facilito la lectura
 
// Inicializa un Nodo en general.
void inicializarNodo(trie &T, int id){
    
    for(int i = 0; i < 10; i++){   
	(T.hijos[i]) = NULL;
    }
    T.id = id;
    T.esHoja = true;
    T.cantHijos = 0;
}

// Arma la solucion.
void armarSolucion(trie &T, string clave){
    
    
    
    clave.push_back(toChar[T.id]);
    
    if (T.esHoja){
	if (T.bill == "invalid"){
	    //No muestro nada
	}
	else{
	    cout << clave << " " << T.bill << endl;
	}
	return;    
    }
    
    for (int i = 0; i < 10; i++){
	if (!((T.hijos[i]) == NULL)){
	    
	    armarSolucion(*(T.hijos[i]), clave);
	    delete T.hijos[i];
	}
    }
}



//Verifica si el nodo del trie ya está definido.
bool existeNodo(int id, trie &T){
    
    return ((T.hijos[id]) != NULL);
}


bool hayHijo(trie &T){
    
    return !T.esHoja;

}


// Si hay alguna hoja completa el resto, sino fija como hoja el nodo actual.
int completarHojas(trie &T, string &valor){
    
    bool hayAlgunHijo = hayHijo(T);
    int i;
    int res = 0;
    
    if(T.cantHijos == 10){
    
    return 0;
    }
    if(hayAlgunHijo){
	
	for(i = 0; i < 10; i++){
	    if ((T.hijos[i]) == NULL){
		trie *nuevo = new trie;
		inicializarNodo(*nuevo, i);
		(*nuevo).bill = valor;
		T.esHoja = false;
		(T.hijos[i]) = nuevo;
		T.cantHijos++;
		if (valor == "invalid"){
		    res += 0;
		}
		else{
		    res+= 1;
		}	
		//cout << T.id << res << endl;
	    }    
	  else{
	    res += completarHojas(*(T.hijos[i]), valor);	
	    }
	}
    }
    
    return res;

}



//Inserta una clave en un trie.
int insertar(int clave[], string &valor, trie &T, int i,  int N){
    
    int id = clave[i];
    //cout << "Entro" << endl;
    if(i == N - 1){
	
	if(!existeNodo(id, T)){
	    //cout << "Deberia entrar" << endl;
	    trie *nuevo = new trie;
	    inicializarNodo(*nuevo, id);
	    (T.hijos[id]) = nuevo;
	     T.esHoja = false;
	     T.cantHijos++;	
	     (*(T.hijos[id])).bill = valor;
	     if (valor == "invalid"){
		return 0;
	     }
	     else{
		return 1;
	    }    
	    
	    //mostrarTrie(T);
	}			
	else{
	//mostrarTrie(T);
	//cout << "Antes de hojas" << endl;
	return completarHojas(*(T.hijos[id]), valor);
	}
	//cout << "Despues de hojas" << endl;
	//mostrarTrie(T);
	    
    }
    if(!existeNodo(id, T)){
	
	trie *nuevo = new trie;
	inicializarNodo(*nuevo, id);
	T.esHoja = false;
	T.cantHijos++;
	//cout << id << endl;
	(T.hijos[id]) = nuevo;
    }			
    //cout << "PUDE AGREGAR ALGO" << endl;
    
    return insertar(clave, valor, *(T.hijos[id]), i+1, N);
    //cout << "Se garca el mostrar" << endl;
    //mostrarTrie(T);
    
}

bool yaEstaOHayPrefijo(int clave[], trie &T, int i,  int N){
    
    
    
    if(i == N-1){
	if(!existeNodo(clave[i], T)){
	    //cout  << "Sali por aca" << endl;
	    return false;
	}
	else{
	    if (hayHijo(*(T.hijos[clave[i]]))){
		//cout  << "Sali por aca" << endl;
		//cout  << "hijo " << (*(T.hijos[clave[i]])).id << endl;
		//cout  << "cantHijos " << (*(T.hijos[clave[i]])).cantHijos << endl;
		
		if ((*(T.hijos[clave[i]])).cantHijos == 10){
		    return true;
		}
		else{
		    return false;
		}
	    }
	    else{
		//cout  << "Sali por aca" << endl;
		return true;
	    }
	}
    }
    else{
    
	if(!existeNodo(clave[i], T)){
	   // cout  << T.id << clave[i] << "Sali por aca" << endl;
	    return false;
	}
	else{
	    if ((*T.hijos[clave[i]]).esHoja){
		//cout  << "Sali por aca" << endl;
		return true;
	    }
	    else{
		return yaEstaOHayPrefijo(clave, *(T.hijos[clave[i]]), i+1,N);
	    }
	}		
    }
}


// Si no esta definida la clave o algún prefijo de ella inserta la clave.
int insertarSiPuedo(int clave[], string &valor, trie &T, int i,  int N){
    
    if(!yaEstaOHayPrefijo(clave, T, 0, N)){
	//cout << "Puedo insertarlo" << endl;
	return insertar(clave, valor, T, 0, N);
    }
    return 0;
} 


int main()
{
    int clave1[3] = {2,2,2};
    string valor1 = "invalid";
    
    int clave2[4] = {2,2,2,1};
    string valor2 = "cuatro";
    
    int clave3[5] = {3,3,3,3,3};
    string valor3 = "cinco";
    
    int clave4[2] = {1,2};
    string valor4 = "dos";
    
    int clave5[1] = {1};
    string valor5 = "uno";
    
    int clave6[3] = {1,2,4};
    string valor6 = "ojo";
    
    int res = 0;
    
    trie inicial;
    inicializarNodo(inicial, -1);  
    //mostrarTrie(inicial, -1);
    //cout << "PASE 1" << endl;
    res +=  insertarSiPuedo(clave1, valor1, inicial, 0, 3);      
    //mostrarTrie(inicial, -1);
    //cout << "PASE 2" << endl;
    res +=  insertarSiPuedo(clave2, valor2, inicial, 0, 4);      
    //mostrarTrie(inicial, -1);
    //cout << "PASE 3" << endl;
    res +=  insertarSiPuedo(clave3, valor3, inicial, 0, 5);      
    //mostrarTrie(inicial, -1);
    //cout << "PASE 4" << endl;
    res +=  insertarSiPuedo(clave4, valor4, inicial, 0, 2);      
    //mostrarTrie(inicial, -1);
    //cout << "PASE 5" << endl;
    res += insertarSiPuedo(clave5, valor5, inicial, 0, 1);      
    //mostrarTrie(inicial, -1);
    //cout << "PASE 6" << endl;
    res += insertarSiPuedo(clave6, valor6, inicial, 0, 3);      
    
    cout << res << endl; 
    armarSolucion(inicial,"");
    //cout << "PASE 7" << endl;
    
    
    
    
    
    return 0;
 
}
